/*
    about double linklist
*/

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>

typedef struct DuNode {
    int data;
    struct DuNode *next;
    struct DuNode *front;
}DuNode;

typedef struct {
    DuNode *head, *tail;
    int length;
}DuLinklist;

//declare
void InitList_Du(DuLinklist *L);
void push_back(DuLinklist *L, int data);
DuNode* _buyDunode(int data);
void printlist_Du(DuLinklist L);


void InitList_Du(DuLinklist *L) {
    L->head = (DuNode*)malloc(sizeof(DuNode));
    L->head = L->tail;
    L->tail->next = NULL;
    L->tail->front = NULL;
    L->length = 0;
    printf("double linklits inited.\n");
}

void CreateList_du(DuLinklist *L, int n) {
    InitList_Du(L);
    int data;
    printf("input data:\n");
    for(int i = 0; i < n; i++) {
        scanf("%d", &data);
        push_back(L, data);
    }
    L->length = n;
    printf("created.\n");
}

void push_back(DuLinklist *L, int data) {
    DuNode *p = _buyDunode(data);
    assert(p);
    L->tail->next = p;
    p->front = L->tail;
    L->tail = p;
    L->length++;
}

DuNode* _buyDunode(int data) {
    DuNode *p = (DuNode*)malloc(sizeof(DuNode));
    p->next = NULL;
    p->front = NULL;
    p->data = data;
    return p;
}

void printlist_Du(DuLinklist L) {
    if(L.length == 0) {
        printf("list is empty!\n");
        return;
    }
    printf("linklist Below:\n");
    DuNode *p = L.head->next;
    for(int i = 0; i < L.length; i++) {
        printf("%d ", p->data);
        p = p->next;
    }
}

void remove_du(DuLinklist *L, int data) {
    DuNode *p = L->head->next;
    while(p->next != NULL) {
        if(p->data == data) {
            if(p == L->tail) {
                L->tail = p->front;
                p->front = NULL;
                L->tail->next = NULL;
            }
            p->front->next = p->next;
            p->next->front = p->front;
            break;
        }
        p = p->next;
    }
    free(p);
    L->length--;
    printf("deleted.\n");
}

int main(int argc, char const *argv[])
{
    DuLinklist L;
    int len;
    printf("input n:\n");
    scanf("%d", &len);
    CreateList_du(&L, len);
    printlist_Du(L);

    printf("\nnow we delete a data:\n");
    remove_du(&L, 1);
    printlist_Du(L);
    return 0;
}
